1、在旋转数组中查找某个数
思想：二分查找，但是此时二分得分情况，mid左半部分有序，还是右半部分有序，如果左半部分有序，那么判断是在左边还是在右边，
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @param target int整型 
     * @return int整型
     */
    int search(vector<int>& nums, int target) {
        // write code here
        int l=0,r=nums.size()-1;
        while(l<=r)
        {
            int mid=(l+r)/2;
            if(nums[mid]==target)
                return mid;
            //左半部有序l到r
            if(nums[l]<=nums[mid])
            {
                //target在左半部
                if(nums[l]<=target&&nums[mid]>target)
                    r=mid-1;
                //target在右半部
                else
                    l=mid+1;
            }
            //右半部有序
            else
            {
                if(nums[mid]<target&&target<=nums[r])
                    l=mid+1;
                else
                    r=mid-1;
            }
        }
        return -1;
    }
};
2、求平方根
思想：i^2<x<(i+1)^2,那么i就是x的平方根
class Solution {
public:
    /**
     * 
     * @param x int整型 
     * @return int整型
     */
    int sqrt(int x) {
        // write code here
        for(int i=0;i<=x;i++)
        {
            if(i*i<=x&&(i+1)*(i+1)>x)
                return i;
        }
        return 0;
    }
};
